Arrays in Compiler

  • How does compiler work with Two Dimensional arrays

How does the compiler work with Two Dimensional Arrays

This applies to Two dimensional arrays.

Picture

int A[3][4]

This will be equal to 12 locations.

How does the compiler do the mapping:

Two methods are used:

  1. Row-major Mapping
  2. Column-major Mapping

Row Major Mapping

This is for indexes that starts at 0

RowMaj.png

int A[3][4]

And we need to convert: A[1][2] to and address.

It is linear in memory, with addresses from 200/1 - 222/23

But visually it is represented in row and column matrix.

We assign for each address its row and column index

$$ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline \text{index}\T& 1\T&2\T&3\T&4\T&5\T&6\T&7\T&8\T&9\T&10\T&11\T&12 \\\hline \text{array}\T&A_{00}\T&A_{01}\T&A_{02}\T&A_{03}\T&A_{10}\T&A_{11}\T&A_{12}\T&A_{13}\T&A_{20}\T&A_{21}\T&A_{22}\T&A_{23} \\\hline \text{address}\T&_{200/201}\T&_{2/3}\T&_{4/5}\T&_{6/7}\T&_{8/9}\T&_{10/11}\T&_{12/13}\T&_{14/15}\T&_{16/17}\T&_{18/19}\T&_{20/21}\T&_{222/223} \\\hline \end{array} $$$$ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|r|r|r|r|} \hline A_{00} \T & A_{01} \T & A_{02} \T & A_{03} \\\hline A_{10} \T & A_{11} \T & A_{12} \T & A_{13} \\\hline A_{20} \T & A_{21} \T & A_{22} \T & A_{23} \\\hline \end{array} $$

But for row major mapping we start off by filling the rows linearly.

E.g.

$$\text{Address of A[0][0]} = A_{00}$$$$\text{Address of A[0][1]} = A_{01}$$$$\text{Address of A[0][2]} = A_{02}$$$$\text{Address of A[0][3]} = A_{03}$$

This will be identified as $row_{0}$

$$\text{Address of A[1][0]} = A_{10}$$$$\text{Address of A[1][1]} = A_{11}$$$$\text{Address of A[1][2]} = A_{12}$$$$\text{Address of A[1][3]} = A_{13}$$

This will be identified as $row_{1}$

$$\text{Address of A[2][0]} = A_{20}$$$$\text{Address of A[2][1]} = A_{21}$$$$\text{Address of A[2][2]} = A_{22}$$$$\text{Address of A[2][3]} = A_{23}$$

This will be identified as $row_{2}$

To get the address for A[1][2]: $$ $$ $$\text{Address of A[1][2]} = 200 + [1\times4 + 2]\times 2$$ $$ $$

$$\text{Address of A[1][2]} = 212$$

To get the address for A[2][3]: $$ $$

$$\text{Address of A[2][3]} = 200 + [2\times4 + 3]\times 2$$$$ $$$$\text{Address of A[2][3]} = 222$$$$ $$$$ $$

Address of any location - ROW MAJOR FORMULA USED BY COMPILER:

$$\text{Address of A[i][j]} = L_0 + [i\times n + j]\times w$$$$ $$$$(\text{int } A[m][n])$$$$(\text{int } A[i][j])$$$$ $$$$\text{where } i = \text{the row index}$$$$\text{where } j = \text{the column index}$$$$\text{where } m = \text{total rows of array}$$$$\text{where } n = \text{total colums of array}$$$$ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|r|r|} \hline i\T & \text{row index} \\\hline j\T & \text{column index} \\\hline m\T & \text{total rows of array} \\\hline n\T & \text{total columns of array} \\\hline w\T & \text{size of data type in bytes} \\\hline \end{array} $$$$ $$$$ $$

Row Major Mapping (where index starts at 1)

This is for indexes that starts at 1

int A[1..3][1..4]

$$ $$

Address of any location - ROW MAJOR FORMULA USED BY COMPILER (index starts at 1):

$$\text{Address of A[i][j]} = L_0 + [(i-1)\times n + (j-1)]\times w$$$$ $$

Where we having 6 operations, compared to 4 operations in case of index that starts at 0.

So definitely more faster for indexes that starts at 0 (i.e. C++).

In [ ]: